#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
    ElemType *elem; //整形指针，申请的堆空间起始地址存入elem
    int TableLen;   //存储动态数组里边元素的个数
}SSTable;

//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    //多申请一个位置，为了存哨兵，不适用哨兵也可以，为了和王道书保持一致
    ST.TableLen=len+1;
    ST.elem= (ElemType *)malloc(sizeof(ElemType)*ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 1; j < ST.TableLen; ++j) //因为第0个是哨兵，所以从1开始
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}

//打印顺序表
void ST_Print(SSTable ST)
{
    for (int i = 1; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
//顺序查找
int Search_Seq(SSTable ST,ElemType key)
{
    ST.elem[0]=key; //key存零号位置，为哨兵，有了这个，我们在循环时，可以少写一个i>0=判断
    int i;
    for (i = ST.TableLen-1; ST.elem[i]!=key; i--); //从后往前找，找到了，i就刚好是对应位置
    return i;
}
//顺序查找
int main() {
    SSTable ST;
    ElemType key;
    ST_Init(ST,10);
    ST_Print(ST); //打印顺序表中的元素
    int pos; //存取查询元素的位置
    printf("please input key:\n");
    scanf("%d",&key);
    pos=Search_Seq(ST,key);
    if(pos)
    {
        printf("find key, position=%d\n",pos);
    } else{
        printf("not find!\n");
    }
    return 0;
}
